package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/
 * @create 2025/9/29 16:26
 * @since JDK17
 */

public class Solution89 {
    List<Integer>[] g;
    char[] s;
    int[] dfs(int cur) {
        // 0 : 一定要从头出发最大的长度 1 : 整棵树最大的长度
        if (g[cur].size() == 0) {
            return new int[]{1, 1};
        }
        int max = 1, first = 0, second = 0;
        for (int u : g[cur]) {
            var x = dfs(u);
            max = Math.max(max, x[1]);
            if (s[cur] != s[u]) {
                if (x[0] > first) {
                    second = first;
                    first = x[0];
                } else if (x[0] > second) {
                    second = x[0];
                }
            }
        }
        int t = first + 1;
        return new int[]{t, Math.max(max, t + second)};
    }

    public int longestPath(int[] parent, String s) {
        g = new List[parent.length];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 1; i < parent.length; i++) {   // 建图
            g[parent[i]].add(i);
        }
        this.s = s.toCharArray();
        return dfs(0)[1];
    }
}
